class Solution
{
    int memo[31];
public:
    int fib(int n)
    {
        memset(memo, -1, sizeof(memo));
        return dfs(n);
    }

    int dfs(int n)
    {
        if (memo[n] != -1) return memo[n];

        if (n == 1 || n == 0) return n;
        memo[n] = dfs(n - 1) + dfs(n - 2);
        return memo[n];
    }
};